\subsection{Characterizing personalized equilibria in two player games} \label{sec:two-player-personalized}
\def\R{\mathbb{R}}
\def\Reals#1{\mathbb{R}^{#1}}
\def\payoff#1{\mbox{\rmfamily Payoff (#1)}}

We can simplify the definition of personalized equilibria when discussing two player games. Consider a matrix game $(R,C)$ between two
players ROW and COLUMN, in which player ROW has strategies $r_1, r_2,
\ldots, r_{m}$, and player COLUMN has strategies $c_1, c_2, \ldots,
c_{n}$. $R \in \Reals{m\times n}$ is the payoff matrix of ROW, and $C
\in \Reals{m\times n}$ is the payoff matrix of COLUMN.

Like a standard bimatrix game, if player ROW selects $r_{i}$ and
  player COLUMN selects $c_{j}$, the payoff to ROW is $R[i,j]$ and the
  payoff to COLUMN is $C[i,j]$.  Suppose ROW selects a distribution
  $x$ among the strategies $\{r_1, r_2, \ldots, r_{m}\}$, and COLUMN
  selects a distribution $y$ among $\{c_1, c_2, \ldots, c_{n}\}$.
  Unlike payoffs defined for mixed strategies, in which the payoff to
  ROW is $\sum_{i,j} x[i]y[j] R[i,j]$ and the payoff to 
  COLUMN is $\sum_{i,j} x[i]y[j] C[i,j]$, we define the
  payoffs using flows.  The payoff to ROW is:
%\vspace{-2mm}
%\begin{equation}
%\payoff{ROW}  = \max_{u_{i,j}} \sum_{i,j} u_{i,j} R[i,j]  \mbox{:  \bf subject to   }
%  \sum_{j} u_{i,j} = x[i], \forall i \mbox{,  and  } \sum_{i} u_{i,j} = y[j], \textrm{ }\forall j; \label{Eqn:ROW}
%\end{equation}
\begin{align}
\payoff{ROW}  = & \quad  \max_{u_{i,j}} \sum_{i,j} u_{i,j} R[i,j] \label{Eqn:ROW}\\
 & \quad \mbox{\bfseries subject to  } 
  \sum_{j} u_{i,j} = x[i], \quad  \forall i \nonumber \\
  & \qquad \mbox{and } \qquad \sum_{i} u_{i,j} = y[j], \quad  \forall j; \nonumber \\
\payoff{COLUMN}  = & \quad  \max_{v_{i,j}}\sum_{i,j} v_{i,j} C[i,j]   \label{Eqn:COLUMN}\\
 & \quad \mbox{\bfseries subject to  } 
  \sum_{j} v_{i,j} = x[i], \quad  \forall i \nonumber \\
  & \qquad \mbox{and} \qquad \sum_{i} v_{i,j} = y[j], \quad  \forall j. \nonumber
\end{align}
%\vspace{-2mm}
%The payoff to player COLUMN is defined symmetrically.
In other words, $\payoff{ROW}$ is the cost of a 1-unit min-cost
  flow from source $r$  to destination $c$ in 
  the directed graph $G_{R}  = (V_{R}, E_{R})$,
  with %$V_{R} = \{r,c, r_1, r_2, \ldots, r_{m}, c_1, c_2, \ldots, c_{n}\}$, 
%$E_{R} =  \{(r \rightarrow r_{i}), \ \forall i\} \cup \{ (r_{i}\rightarrow c_{j}), \ \forall i, j\} \cup \{(c_{j} \rightarrow c),\ \forall j \}$,
%\junk{
\vspace{-2mm}
\begin{eqnarray*}
 V_{R} & = & \{r,c, r_1, r_2, \ldots, r_{m}, c_1, c_2, \ldots,
  c_{n}\} \\
E_{R} & =  &\{(r \rightarrow r_{i}), \ \forall i\} \cup 
             \{ (r_{i}\rightarrow c_{j}), \ \forall i, j\} \cup 
             \{(c_{j} \rightarrow c),\ \forall j \},
\end{eqnarray*}
%}
%\vspace{-2mm}
where the capacity of edge $(r \rightarrow r_{i})$ is $x[i]$, the
capacity of edge $(c_{j} \rightarrow c)$ is $y[j]$, and the capacity
of all other edges is $+\infty$.  The cost of edge $(r_{i}\rightarrow
c_{j})$ is $-R[i,j]$, and the cost of all other edges is 0.  We note
that for any distributions $x$ and $y$, a unit-flow from $r$ to $c$
always exists, so the above payoff function is well-defined.
%$\payoff{COLUMN}$ is defined in symmetric fashion. 

%\junk{ 
Similarly, $\payoff{COLUMN}$ is the cost of a 1-unit minimum-cost
  flow from source $c$  to destination $r$ in the directed graph $G_{C}  = (V_{C}, E_{C})$,
  with
\begin{eqnarray*}
 V_{C} & = & \{r,c, r_1, r_2, \ldots, r_{m}, c_1, c_2, \ldots,
  c_{n}\} \\
E_{C} & =  &\{(c \rightarrow c_{j}), \ \forall j\} \cup 
             \{ (c_{j}\rightarrow r_{i}), \ \forall i, j\} \cup 
              \{(r_{i} \rightarrow r),\ \forall i \},
\end{eqnarray*}
where the capacity of edge $(c \rightarrow c_{j})$ is $y[j]$,
the capacity of edge $(r_{i} \rightarrow r)$ is $x[i]$, and 
the capacity of all other edges is $+\infty$. The cost of edge $(c_{j}\rightarrow r_{i})$ is $-C[i,j]$, and
  the cost of all other edges is 0.
%}

\junk{
Because there is no condition such as $u[i,j] = v[i,j]$ in
   Eqn. (\ref{Eqn:ROW}), (or in the payoff function for COLUMN) %and Eqn. (\ref{Eqn:COLUMN}),
  each player can individually choose the best way to match 
  the distributions.
We therefore refer to these payoff functions as \emph{personalized payoff
  functions}, and we call an equilibrium for the game with
   these payoffs a \emph{personalized equilibrium}.
Using personalized payoffs, 
  each player plays a distribution across her strategy space and
\emph{chooses} how to combine it with the strategy distributions of the other players.
}
\junk{
This concept of personalized equilbria is inspired by the correlated equilibrium of Aumann (\cite{Aumann}).
Recall that the correlated payoff function requires $u_{i,j} = v_{i,j}$
  in  Eqn. (\ref{Eqn:ROW}) and Eqn. (\ref{Eqn:COLUMN}),
  but relaxes Nash's condition of $u_{i,j} = v_{i,j} = x[i]y[j]$.
We are considering payoff functions (personalized payoff functions) which futher relax this by removing $u_{i,j} = v_{i,j}$.
}
\junk{
One can extend the personalized payoff functions to multi-player
matrix games.  Suppose we are given a $k$-player matrix game $G$, with
$S_i$ being a set of $m_i$ strategies for player $i$, $1 \le i \le
k$, and $u_i: \prod_j S_j \rightarrow {\mathbb R}$ being the utility
function for player $i$.  As in a mixed strategy, each player $i$
chooses a probability distribution $p_i: S_i \rightarrow [0,1]$ over
the strategies in $S_i$.  Given $p_1$, \ldots, $p_k$, the personalized
payoff function for player $i$ is computed as follows.  Construct a
hypergraph $H_i$ with $V = \cup_j S_j$ as the set of nodes and $E =
\prod_j S_j$ as the set of hyperedges.  Consider a (fractional
hypergraph) matching defined by an assignment $w_i : E \rightarrow
{\mathbb R}$ of weights to each hyperedge that satisfies the condition
that the sum of weights of all hyperedges adjacent to any strategy $s
\in S_j$ (for any $j$) equals $p_j(s)$.  Define the weight of
matching $w_i$ as $\sum_{e \in E} w_i(e) u_i(e)$.  The payoff to
player $i$ is then simply the cost of the maximum-weight matching in
$H_i$.

The concept of personalized equilibria is extendible to games with succinct
representations such as graphical games \cite{KearnsLittmanSingh}
and multimatrix games \cite{Yanovskaya}. It can also be viewed as a relaxation of correlated
equilibrium \cite{Aumann}. Here we are primarily concerned with sparse personalized matrix games: games in which only a polynomial (in $k$ and $\max_i m_i$) number of hyperedges for each player have non-zero utility.
}

It is not hard to show that the set of all two-player personalized
  equilibria is convex.
In fact, we can give a stronger characterization, which will lead to
  a polynomial time algorithm.

\begin{theorem}
A 2-player personalized equilibrium can always be found in polynomial time.
\end{theorem}

\begin{proof}
\junk{
Recall the secondary definition of the personalized payoff to player ROW in a two-player game given at the start of Section \ref{sec:personalized}: 

$\payoff{ROW}$ is the cost of a 1-unit minimun-cost
  flow from source $r$  to destination $c$ in 
  the directed graph $G_{R}  = (V_{R}, E_{R})$,
  with
\begin{eqnarray*}
 V_{R} & = & \{r,c, r_1, r_2, \ldots, r_{m}, c_1, c_2, \ldots,
  c_{n}\} \\
E_{R} & =  &\{(r \rightarrow r_{i}), \ \forall i\} \cup 
             \{ (r_{i}\rightarrow c_{j}), \ \forall i, j\} \cup 
              \{(c_{j} \rightarrow c),\ \forall j \},
\end{eqnarray*}
where the capacity of edge $(r \rightarrow r_{i})$ is $x[i]$, the
capacity of edge $(c_{j} \rightarrow c)$ is $y[j]$, and the capacity
of all other edges is $+\infty$.  The cost of edge $(r_{i}\rightarrow
c_{j})$ is $-R[i,j]$, and the cost of all other edges is 0. 

A similar definition of a flow on a graph $G_{C}$ gives the payoff function for player COLUMN. 
}
Let graph $G = $ the union of $G_{R}$ and $G_{C}$. We will now consider a subgraph $G'= (V',E') \subset G$, such that $V' = V_{R} \cap V_{C}$, $(r_i \rightarrow c_j) \in E_R$ is in $E'$ if and only if $R[i,j] \geq R[i',j]$ for all $i'$, and $(c_j \rightarrow r_i) \in E_C$ is in $E'$ if and only if $C[i,j] \geq C[i,j']$ for all $j'$.

%\begin{prop}
\medskip
\BfPara{Any directed cycle in $G'$ corresponds to a personalized equilibrium}
%\end{prop}
Consider any cycle \\ $\{r_{i1}, c_{j1}, r_{i2}, c_{j2}, \ldots, r_{il}, c_{il}\}$ in $G'$, each node played with weight $\frac{1}{l}$. Player ROW can match each of his strategies $r_{ik}$ with player COLUMN's strategy $c_{jk}$. Since this is a best response for player ROW, ROW cannot
do better by changing to another strategy. Similarly, player ROW can match each of his strategies $c_{jk}$ with player ROW's strategy $r_{i(k+1)}$ for $k < l$, $c_{jl}$ can be matched with $r_{i1}$. 

\medskip
%\begin{prop}
\BfPara{Every personalized equilibrium is a linear combination of cycles in $G'$}
%\end{prop}
Starting with any bipartite graph from $G'$ in which the in-degree
equals the out-degree of each node (a characteristic of any
personalized equilibrium), we can remove any cycle (which is a personalized equilibrium) and we are still
left with a bipartite graph with the same characteristic. 
\end{proof}